package genetic.q1;

import genetic.Genotype;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class TSPGreedy {
	TSPGraph graph;
	public TSPGreedy(TSPGraph graph){
		this.graph = graph;
	}

	public TSPGenotype solve(int start){
		List<Integer> tmp = new LinkedList<Integer>();
		for (int i=0; i<graph.getSize(); i++) if (i!=start){
			tmp.add(i);
		}
		int totalDist = 0;
		Vector<Integer> route = new Vector<Integer>();
		route.add(start);
		int curCity = start;
		while (!tmp.isEmpty()){
			int minDist = Integer.MAX_VALUE;
			int minCity = 0;
			for (int j=0; j<tmp.size(); j++){
				int dist = graph.getDistance(curCity, tmp.get(j));
				if (dist<minDist){
					minDist = dist;
					minCity = j;
				}
			}
			curCity = tmp.remove(minCity);
			route.add(curCity);
			totalDist+=minDist;
		}
		totalDist += graph.getDistance(curCity, start);
		System.out.println("Distance " + totalDist + " - " + Arrays.toString(route.toArray()));
		int[] arr = new int[graph.getSize()];
		for (int i=0; i<route.size(); i++){
			arr[i] = route.get(i)+1;
		}
		System.out.println(new TSPGenotype(arr, graph));
		return new TSPGenotype(arr, graph);
	}
	
	public List<Genotype> getPopulation(int size){
		List<Genotype> ans = new LinkedList<Genotype>();
		for (int i=0; i<size; i++){
			ans.add(solve(i % graph.getSize()));
		}
		return ans;
	}
	public static void main(String[] args) {
		TSPGraph g = new TSPGraph("TSP1.txt");
		g.readFile();
		for (int i=0; i<g.getSize(); i++){
			System.out.println("i=" +i);
			new TSPGreedy(g).solve(i);
		}
	}
}
